package solution;

import java.util.*;

/**
 * @author zhangmin
 * @create 2021-11-05 12:59
 */
public class Solution_13interview {


    /**===========================================================================================================================
     * 659. 分割数组为连续子序列
     * 给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个长度至少为 3 的子序列，其中每个子序列都由连续整数组成。如果可以完成上述分割，则返回 true ；否则，返回 false 。
     * */
    public boolean isPossible(int[] nums) {
        //freq记录nums每个元素出现的次数
        HashMap<Integer,Integer> freq=new HashMap<>();
        //need记录哪些元素可以被接到其他子序列后面。统计这些元素可以在其他多少个子序列后面，即需求
        HashMap<Integer,Integer> need=new HashMap<>();
        for (int num:nums) {
            freq.put(num,freq.getOrDefault(num,0)+1);
        }
        for (int v:nums) {
            if (freq.getOrDefault(v,0)==0){
                // 已经被用到其他子序列中
                continue;
            }
            // 先判断 v 是否能接到其他子序列后面
            if (need.containsKey(v)&&need.get(v)>0){
                freq.put(v,freq.getOrDefault(v,0)-1);
                need.put(v,need.get(v)-1);
                need.put(v+1,need.getOrDefault(v+1,0)+1);
            }else if (freq.get(v)>0&&freq.getOrDefault(v+1,0)>0&&freq.getOrDefault(v+2,0)>0){
                // 将 v 作为开头，新建一个长度为 3 的子序列 [v,v+1,v+2]
                freq.put(v,freq.getOrDefault(v,0)-1);
                freq.put(v+1,freq.getOrDefault(v+1,0)-1);
                freq.put(v+2,freq.getOrDefault(v+2,0)-1);
                need.put(v+3,need.getOrDefault(v+3,0)+1);
            }else {
                // 两种情况都不符合，则无法分配
                return false;
            }
        }
        return true;
    }


    /**===========================================================================================================================
     * 牛客 吃葡萄
     * 有三种葡萄，每种分别有 a, b, c 颗，现在有三个人，第一个人只吃第一种和第二种葡萄，第二个人只吃第二种和第三种葡萄，第三个人只吃第一种和第三种葡萄。
     * 现在给你输入 a, b, c 三个值，请你适当安排，让三个人吃完所有的葡萄，算法返回吃的最多的人最少要吃多少颗葡萄。
     * 思路：吃得最多的那个人吃得最少」就是让我们尽可能地平均分配，
     * 如果把葡萄的颗数 a, b, c 作为三条线段，它们的大小作为线段的长度，想一想它们可能组成什么几何图形？我们的目的是否可以转化成「尽可能平分这个几何图形的周长」？
     * 如果 a + b > c，那么可以构成一个三角形，只要在这个三角形中间画一个顶点都在边 a, b, c 上的等边三角形，这三点就一定可以把这个三角形的周长平分成三份，且每一份都包含两条边，这种情况下，三个人依然是可以平均分配所有葡萄的
     * 如果 a + b <= c，这三条边就不能组成一个封闭的图形了，那么我们可以将最长边 c「折断」，也就是形成一个四边形。
     *          对于情况一，a + b 和 c 的差距还不大的时候，可以看到依然能够让三个人平分这个四边形，那么吃的最多的人最少可以吃到的葡萄颗数依然是 (a+b+c+2)/3
     *          情况二：随着 c 的不断增大，就会出现情况二，此时 c > 2*(a+b)，由于每个人口味的限制，为了尽可能平分，X 最多吃完 a 和 b，而 c 边需要被 Y 或 Z 平分，也就是说此时吃的最多的人最少可以吃到的葡萄颗数就是 (c+1)/2，即平分 c 边向上取整。
     * */
    long solution(long a, long b, long c) {
        long[] nums=new long[]{a,b,c};
        Arrays.stream(nums);
        long sum=a+b+c;
        // 能够构成三角形，可完全平分
        if (nums[0]+nums[1]>nums[2])
            return (sum+2)/3;
        // 不能构成三角形，平分最长边的情况
        if (2*(nums[0]+nums[1])<nums[2]){
            return (nums[2]+1)/2;
        }
        // 不能构成三角形，但依然可以完全平分的情况
        return (sum+2)/3;
    }


    /**===========================================================================================================================
     * 969. 煎饼排序
     * 给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。一次煎饼翻转的执行过程如下：选择一个整数 k ，1 <= k <= arr.length,反转子数组 arr[0...k-1]（下标从 0 开始）
     * 以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。
     * */
    List<Integer>res969=new LinkedList<>();
    void reverse(int[] arr,int i,int j){
        while (i<j){
            int temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
            i++;j--;
        }
    }
    //煎饼排序arr[0...n-1]
    void sort(int[] arr,int n){
        // base case
        if (n==1) return;
        // 寻找最大饼的索引
        int maxNum=0;
        int maxIndex=0;
        for (int i = 0; i < n; i++) {
            if (arr[i]>maxNum){
                maxNum=arr[i];
                maxIndex=i;
            }
        }
        // 第一次翻转，将最大饼翻到最上面
        reverse(arr,0,maxIndex);
        res969.add(maxIndex+1);
        // 第二次翻转，将最大饼翻到最下面
        reverse(arr,0,n-1);
        res969.add(n);
        sort(arr,n-1);
    }
    public List<Integer> pancakeSort(int[] arr) {
        sort(arr,arr.length);
        return res969;
    }



    /**===========================================================================================================================
     * 43. 字符串相乘
     * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
     * 思路：有两个指针 i，j 在 num1 和 num2 上游走，计算乘积，同时将乘积叠加到 res 的正确位置：num1[i] 和 num2[j] 的乘积对应的就是 res[i+j] 和 res[i+j+1] 这两个位置。
     * */
    public String multiply(String num1, String num2) {
        int m=num1.length();
        int n=num2.length();
        // 结果最多为 m + n 位数
        int[] res=new int[m+n];
        // 从个位数开始逐位相乘
        for (int i = m-1; i >=0 ; i--) {
            for (int j = n-1; j >=0 ; j--) {
                int mul=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
                // 乘积在 res 对应的索引位置
                int index1=i+j,index2=i+j+1;
                int sum=mul+res[index2];
                res[index2]=sum%10;
                res[index1]+=sum/10;
            }
        }
        //去除结果中的前缀0
        int i=0;
        while (i<res.length&&res[i]==0){
            i++;
        }
        String s="";
        for (; i < res.length; i++) {
            s+=res[i];
        }
        return s.length()==0?"0":s;
    }



    /**===========================================================================================================================
     * 224. 基本计算器
     * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
     * 1、加减法直接将符号带到数字前入栈
     * 2、乘除法，pop出栈顶元素计算后结果入栈
     * 3、括号--递归，（开始调用，）结束调用
     * */
    String str="";
    public int calculate(String s) {
        str=s;
//        System.out.println("======================================s="+s);
        Stack<Integer> stack=new Stack<>();
        // 记录算式中的数字
        int num=0;
        // 记录 num 前的符号，初始化为 +
        char sign='+';
        while (str.length()>0){
            char c=str.charAt(0);
            str=str.substring(1);
//            System.out.println("=="+c);
            // 如果是数字，连续读取到 num
            if (Character.isDigit(c)){
                num=10*num+(c-'0');
            }
//            System.out.println("curnum="+num);
            if (c=='('){
//                System.out.println("sub="+str);
                num=calculate(str);
//                System.out.println("curnum="+num);
            }
            // 如果不是数字，就是遇到了下一个符号，
            // 之前的数字和符号就要存进栈中
            if (((c!=' ')&&!Character.isDigit(c))||str.length()==0){
//                System.out.println("curC="+c);
                switch (sign){
                    case '+':
                        stack.push(num);break;
                    case '-':
                        stack.push(-num);break;
                    case '*':
                        int pre1=stack.pop();
                        stack.push(pre1*num);break;
                    case '/':
                        int pre2=stack.pop();
                        stack.push(pre2/num);break;
                }
                // 更新符号为当前符号，数字清零
                sign=c;
                num=0;
            }
            if (c==')'){
                break;
            }
//            System.out.println("curSign="+sign);
        }
        int sum=0;
//        System.out.println("stack="+stack);
        while (!stack.isEmpty()){
            sum+=stack.pop();
//            System.out.println("sum="+sum);
        }
        return sum;
    }



    /**===========================================================================================================================
     * 42. 接雨水
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 思路：考虑每个柱子考虑他可以装多少水，water[i] = min(左边最高的柱子max(height[0..i]),  右边最高的柱子max(height[i..end])  ) - height[i]
     * */
    //1、先计算出左右边的最大值，避免重复计算
    public int trap1(int[] height) {
        int n=height.length;
        int[] left_max=new int[n];
        int[] right_max=new int[n];
        left_max[0]=height[0];
        right_max[n-1]=height[n-1];
        for (int i = 1; i < n; i++) {
            left_max[i]=Math.max(height[i],left_max[i-1]);
        }
        for (int i = n-2; i >=0 ; i--) {
            right_max[i] =Math.max(right_max[i+1],height[i]);
        }

        int res=0;
        for (int i = 1; i < n-1; i++) {
            res+=Math.min(left_max[i],right_max[i])-height[i];
        }
        return res;
    }
    //2、双指针:我们只在乎 min(l_max, r_max)
    public int trap(int[] height) {
        int n=height.length;
        System.out.println("n="+n);
        if (n==0)return 0;
        int left=0,right=n-1;
        int res=0;
        int left_max=height[0];
        int right_max=height[n-1];

        while (left<=right){
            System.out.println("left="+left+"         right"+right);
            left_max=Math.max(left_max,height[left]);
            right_max=Math.max(right_max,height[right]);
            System.out.println("left_max="+left_max+"        right_max="+right_max);
            //当left_max<right_max时，当前位置的数量由两种中较小的那个决定，此时的right_max时不一定时最大的，但是不影响当前位置
            if (left_max<right_max){
                res+=left_max-height[left];
                System.out.println("res-l="+res);
                left++;
            }else {
                res+=right_max-height[right];
                System.out.println("res-r="+res);
                right--;
            }
        }
        return res;
    }


    /**===========================================================================================================================
     * 5. 最长回文子串
     * 给你一个字符串 s，找到 s 中最长的回文子串
     * */
    //找到以l和r为中心的最长回文串
    String palindrome(String s, int l, int r) {
        while (l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){
            l--;r++;
        }
        return s.substring(l+1,r);
    }
    public String longestPalindrome(String s) {
        String res="";
        for (int i = 0; i < s.length(); i++) {
            // 以 s[i] 为中心的最长回文子串
            String s1=palindrome(s,i,i);
            // 以 s[i] 和 s[i+1] 为中心的最长回文子串
            String s2=palindrome(s,i,i+1);
            res=res.length()>s1.length()?res:s1;
            res=res.length()>s2.length()?res:s2;
        }
        return res;
    }

    /**===========================================================================================================================
     * 20. 有效的括号
     * */
    char leftOf(char c) {
        if (c == '}') return '{';
        if (c == ')') return '(';
        return '[';
    }
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for (char c:s.toCharArray()) {
            if (c=='('||c=='{'||c=='['){
                stack.push(c);
            }else {
                if (!stack.isEmpty()&&leftOf(c)==stack.peek()){
                    stack.pop();
                }else
                    return false;
            }
        }
        return stack.isEmpty();
    }


    /**===========================================================================================================================
     * 921. 使括号有效的最少添加
     * 给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
     * 核心思路是以左括号为基准，通过维护对右括号的需求数 need，来计算最小的插入次数。
     * */
    public int minAddToMakeValid(String s) {
        int res=0;
        int need=0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)=='('){
                // 对右括号的需求 + 1
                need++;
            }
            if (s.charAt(i)==')'){
                need--;
                if (need==-1){
                    need=0;
                    // 需插入一个左括号
                    res++;
                }
            }
        }
        return res+need;
    }



    /**===========================================================================================================================
     * 1541. 平衡括号字符串的最少插入次数
     * 现在假设 1 个左括号需要匹配 2 个右括号才叫做合法的括号组合，那么给你输入一个括号串 s，请问你如何计算使得 s 合法的最小插入次数呢？
     * 核心思路还是和刚才一样，通过一个 need 变量记录对右括号的需求数，根据 need 的变化来判断是否需要插入。
     * */
    public int minInsertions(String s) {
        int res=0;
        int need=0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)=='('){
                // 对右括号的需求 + 2
                need+=2;
                if (need%2==1){
                    //当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号。。因为一个左括号需要两个右括号嘛，右括号的需求必须是偶数
                    res++;
                    need--;
                }
            }
            if (s.charAt(i)==')'){
                need--;
                if (need==-1){
                    //当 need == -1 时，意味着我们遇到一个多余的右括号，显然需要插入一个左括号。但是由于一个左括号需要两个右括号，所以对右括号的需求量变为 1
                    need=1;
                    // 需插入一个左括号
                    res++;
                }
            }
        }
        return res+need;
    }





    /**===========================================================================================================================
     * 391. 完美矩形
     * 给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。
     * 如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。
     * 通过面积和顶点两个条件判断
     * 1、面积：计算出最终完美矩形的面积，然后和所有小矩形面积之和比较--即便面积相同，并不能完全保证不存在空缺或者重叠，所以我们需要从「顶点」的维度来辅助判断。
     * 2、顶点：完美矩形一定只有四个顶点。当一个点在偶数个小矩形中出现时不是顶点，在奇数个小矩形中出现时是顶点，
     *      用一个set记录出现的顶点，如果某一个顶点 p 存在于集合 points 中，则将它删除；如果不存在于集合 points 中，则将它插入。
     *      筛选出奇数个出现的顶点，还需要判断这写顶点刚好是完美矩形的四个顶点
     * */
    public boolean isRectangleCover(int[][] rectangles) {
        //（X1，Y1）表示完美矩形的左下顶点
        int X1=Integer.MAX_VALUE,Y1=Integer.MAX_VALUE;
        //（X2，Y2）表示完美矩形的右上顶点
        int X2=Integer.MIN_VALUE,Y2=Integer.MIN_VALUE;

        HashSet<String> points=new HashSet<>();
        int actual_area=0;
        for (int[] r:rectangles) {
            int x1=r[0],y1=r[1];
            int x2=r[2],y2=r[3];
            X1=Math.min(X1,x1);
            Y1=Math.min(Y1,y1);
            X2=Math.max(X2,x2);
            Y2=Math.max(Y2,y2);

            // 累加小矩形的面积
            actual_area+=(x2-x1)*(y2-y1);

            //记录最终形成的图形中的顶点
            int[][] curP=new int[][]{{x1,y1},{x1,y2},{x2,y1},{x2,y2}};
            for (int[] p:curP) {
                String ps=p[0]+" "+p[1];
                //如果某一个顶点 p 存在于集合 points 中，则将它删除；如果不存在于集合 points 中，则将它插入。
                if (points.contains(ps)){
                    points.remove(ps);
                }else {
                    points.add(ps);
                }
            }
        }
        int except_area=(X2-X1)*(Y2-Y1);
//        System.out.println("except_area="+except_area+"      actual_area="+actual_area);
        if (actual_area!=except_area)return false;
//        System.out.println(points.size());

        if (points.size()!=4) return false;

        //判断留下的 4 个顶点是否是完美矩形的顶点
        int[][] exceptP=new int[][]{{X1,Y1},{X1,Y2},{X2,Y1},{X2,Y2}};
//        System.out.println(exceptP);
        for (int[] ep:exceptP){
            String esp=ep[0]+" "+ep[1];
            if (!points.contains(esp)) return false;
        }
        return true;
    }


    /**===========================================================================================================================
     * 855. 考场就座
     * 在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1 。当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。
     * 如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)
     * 思路：如果将每两个相邻的考生看做线段的两端点，新安排考生就是找最长的线段，然后让该考生在中间把这个线段「二分」，中点就是给他分配的座位。leave(p) 其实就是去除端点 p，
     * 使得相邻两个线段合并为一个。但凡遇到在动态过程中取最值的要求，肯定要使用有序数据结构，我们常用的数据结构就是二叉堆和平衡二叉搜索树了
     * Java 的一种数据结构 TreeSet，这是一种有序数据结构，底层由红黑树（一种平衡二叉搜索树）维护有序性。
     * */
    class ExamRoom {

        //记录以端点p为左端点的线段
        private Map<Integer,int[]> startMap;
        //记录以端点p为右端点的线段
        private Map<Integer,int[]> endMap;
        //根据线段长度从小到大存放所有线段
        private TreeSet<int[]> treeSet;
        private int n;

        public ExamRoom(int n) {
            this.n=n;
            startMap=new HashMap<>();
            endMap=new HashMap<>();
            treeSet=new TreeSet<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    int d1=distance(o1);
                    int d2=distance(o2);
                    //比较两个线段的长度，从小到大存放，当线段长度相等时，比较索引
                    if (d1==d2) return o2[0]-o1[0];
                    return d1-d2;
                }
            });
            addInterval(new int[]{-1,n});//放入一个虚拟线段当作哨兵
        }
        //distance不能简单地让它计算一个线段两个端点间的长度，而是让它计算该线段中点和端点之间的长度。这样奇数偶数的长度得到相同的长度，就会比较两者的索引
        private int distance(int[] intv) {
            int x=intv[0],y=intv[1];
            if (x==-1) return y;
            if (y==n) return n-1-x;
            // 中点和端点之间的长度
            return (y-x)/2;
        }

        /* 去除一个线段 */
        private void removeInterval(int[] intv) {
            treeSet.remove(intv);
            startMap.remove(intv[0]);
            endMap.remove(intv[1]);
        }
        /* 增加一个线段 */
        private void addInterval(int[] intv) {
            treeSet.add(intv);
            startMap.put(intv[0],intv);
            endMap.put(intv[1],intv);
        }
        //函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置
        public int seat() {
            //从treeSet里取出来最长的线段
            int[] longest = treeSet.last();
            int x=longest[0],y=longest[1];
            int seat;
            if (x==-1){
                seat=0;
            }else if (y==n){
                seat=n-1;
            }else {
                seat=(y-x)/2+x;
            }
            //将这个线段以seat为中点分为两个线段
            int[] left=new int[]{x,seat};
            int[] right=new int[]{seat,y};
            removeInterval(longest);
            addInterval(left);
            addInterval(right);
            return seat;
        }

        //函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在座位 p 上。
        public void leave(int p) {
            //将p的左右两个线段找到
            int[] right = startMap.get(p);
            int[] left = endMap.get(p);
            //将两个线段拼接成一个大的线段
            int[] m=new int[]{left[0],right[1]};
            removeInterval(right);
            removeInterval(left);
            addInterval(m);
        }
    }


    /**===========================================================================================================================
     * 392. 判断子序列
     * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
     * （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
     * 思路：二分查找：
     * */
    // 查找左侧边界的二分查找
    int left_bound(ArrayList<Integer> nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums.get(mid) < target) {
                left = mid + 1;
            } else if (nums.get(mid) > target) {
                right = mid;
            } else if (nums.get(mid) == target) {
                // 别返回，锁定左侧边界
                right = mid;
            }
        }
        return left;
    }
    public boolean isSubsequence(String s, String t) {
        int m=s.length(),n=t.length();
        //对t预处理，记录t中每个字符出现的位置
        ArrayList<Integer>[] index=new ArrayList[256];
        for (int i = 0; i < n; i++) {
            char c=t.charAt(i);
            if (index[c]==null)
                index[c]=new ArrayList<>();
            index[c].add(i);
        }

        int j=0;//在t上的指针
        for (int i = 0; i < m; i++) {
            char c=s.charAt(i);
            // 整个 t 压根儿没有字符 c
            if (index[c]==null) return false;
            int pos=left_bound(index[c],j);
            // 二分搜索区间中没有找到字符 c
            if (pos==index[c].size()) return false;
            j=index[c].get(pos)+1;
        }
        return true;
    }

    public static void main(String[] args) {
        Solution_13interview obj=new Solution_13interview();
        String s="1 + 1";
        int[] nums=new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        int[][] p=new int[][]{{1,1,3,3},{3,1,4,2},{3,2,4,4},{1,3,2,4},{2,3,3,4}};
//        System.out.println(obj.calculate(s));
//        System.out.println(obj.trap(nums));
        System.out.println(obj.isRectangleCover(p));
    }
}
